package com.yueke.gemini.utils;

/**
 * Created by admin on 2017/10/21.
 */
public class SortUtil {



    /**
     *  java实现二分查找两种方法
     * 详细说明参考：http://blog.csdn.net/maoyuanming0806/article/details/78176957
     * 使用递归的二分查找
     *title:recursionBinarySearch
     *@param arr 有序数组
     *@param key 待查找关键字
     *@return 找到的位置
     */
    public static int recursionBinarySearch(int[] arr,int key,int low,int high){

        if(key < arr[low] || key > arr[high] || low > high){
            return -1;
        }

        int middle = (low + high) >>> 1;          //初始中间位置
        if(arr[middle] > key){
            //比关键字大则关键字在左区域
            return recursionBinarySearch(arr, key, low, middle - 1);
        }else if(arr[middle] < key){
            //比关键字小则关键字在右区域
            return recursionBinarySearch(arr, key, middle + 1, high);
        }else {
            return middle;
        }

    }

    /**
     * 方法二：
     * 不使用递归的二分查找
     *title:commonBinarySearch
     *@param arr
     *@param key
     *@return 关键字位置
     */
    public static int commonBinarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;         //定义middle

        if(key < arr[low] || key > arr[high] || low > high){
            return -1;
        }

        while(low <= high){
            middle = (low + high) >>> 1;
            if(arr[middle] > key){
                //比关键字大则关键字在左区域
                high = middle - 1;
            }else if(arr[middle] < key){
                //比关键字小则关键字在右区域
                low = middle + 1;
            }else{
                return middle;
            }
        }

        return -1;      //最后仍然没有找到，则返回-1
    }

    /**
     *   详细分析过程查看：http://blog.csdn.net/maoyuanming0806/article/details/78175732
        直接插入排序的优化方案就是希尔排序，看我的上一个代码片段：java实现希尔排序
     */
    public static void directSort(int[] arr) {

        int waitInsert;         //等待插入的数
        int i,j;            //i表示当前待插入数下标；j表示本次被比较的有序数位置

        for(i = 1; i < arr.length; i++) {
            waitInsert = arr[i];    //得到本轮待插入的数
            j = i - 1;      //比较位置初始化，也就是有序序列的最后一个位置，从后往前

            //若大于或等于等待插入的数值大小，则该数右移，然后进行下一次比较
            while(j > -1 && arr[j] >= waitInsert) {
                arr[j + 1] = arr[j];
                j--;
            }
            //插入的位置一定是上一次比较的数的位置，也就是j+1的位置。（注意到j--的时机即可理解）
            arr[j + 1] = waitInsert;
        }
    }

    /**
     * java实现希尔排序，在直接插入排序之上的优化方案
     * 详细说明文章查看：http://blog.csdn.net/maoyuanming0806/article/details/78176777
     */
    public static void shellSort(int[] arr){

        //初始化增量
        int h = 1;
        //计算最大间隔，公式：h = h * 3 + 1
        while(h < arr.length / 3){
            h = h * 3 + 1;
        }

        //缩小增量进行排序
        while(h > 0){
            //进行插入排序
            int waitInsert;         //等待插入的数
            int i,j;                //i表示当前待插入数下标；j表示本次被比较的有序数位置

            for(i = h; i < arr.length; i++) {
                waitInsert = arr[i];    //得到本轮待插入的数
                j = i - h;              //比较位置初始化，也就是有序序列的最后一个位置，从后往前

                //若大于或等于等待插入的数值大小，则该数右移一个间隔大小，然后进行下一次比较
                while(j > -1 && arr[j] >= waitInsert) {
                    arr[j + h] = arr[j];
                    j = j - h;
                }
                //插入的位置一定是上一次比较的数的位置，也就是j+h的位置。（注意到j-h的时机即可理解）
                arr[j + h] = waitInsert;
            }

            //缩小增量，公式：h = (h - 1) /3
            h = (h - 1) / 3;

        }
    }
}
